Pakowanie [A]

Limit pamięci: 256 MB

Nadszedł czas biwaku! Na biwak trzeba zabrać różne rzeczy, a potem je ze sobą nosić, zatem podjęcie decyzji, które przedmioty są naprawdę niezbędne do skutecznego biwakowania, jest bardzo ważne. Na szczęście nie na tym polega Twoje zadanie, bowiem przedmioty do zapakowania zostały już wybrane. Teraz pozostało tylko zapakować je w plecaki.

Do każdego plecaka można włożyć dowolnie wiele przedmiotów, o ile tylko ich łączna masa nie przekracza jego udźwigu. Przedmiotów nie można dzielić, więc może się okazać, że pojemność użytych plecaków nie zostanie w całości wykorzystana.

Problem w tym, że plecaków jeszcze nie ma i trzeba je kupić. W sklepie dostępne są różne modele plecaków. Każdy plecak charakteryzuje się ustalonym udźwigiem, cena wszystkich plecaków jest jednakowa. Twoim zadaniem jest kupić plecaki, które wystarczą do zapakowania wszystkich przedmiotów na biwak oraz wydać przy tym jak najmniej.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (, ), określające liczbę przedmiotów do zapakowania oraz liczbę dostępnych plecaków. W drugim wierszu znajduje się ciąg liczb całkowitych (); liczba określa masę -tego przedmiotu. W trzecim wierszu znajduje się ciąg liczb całkowitych (); liczba określa udźwig -tego plecaka.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita będąca minimalną liczbą plecaków wystarczających do zapakowania wszystkich przedmiotów. Jeżeli zapakowanie przedmiotów nie jest możliwe, należy zamiast tego wypisać na wyjście jedno słowo NIE.

Przykład

Dla danych wejściowych:

4 3
4 2 10 3
11 18 9

poprawną odpowiedzią jest:

2

Wyjaśnienie do przykładu: Można na przykład zakupić pierwszy i trzeci plecak. Najcięższy przedmiot może się wówczas znaleźć w plecaku o pojemności , zaś do plecaka o pojemności można włożyć pozostałe przedmioty.

Autor zadania: Danny Sleator.